Regular expressions provide a concise and formal way of describing a set of strings over an alphabet. Given a regular expression and a string, the regular expression matches the string if the string belongs to the set described by the regular expression. Regular expression matching may be used, for example, by command shells, programming languages, text editors, and search engines to search for text within a document. Known techniques for regular expression matching can have long worst-case matching times.